\F46. Game trees.\F0

\J	The positions that can be reached from an initial position in
a  game  form  a  tree, and deciding what move to make often involves
searching this tree.  However, game trees are searched in a different
way  than the trees we have looked at, because the opposing interests
of the players makes it not a search for a joint line  of  play  that
will  lead  to  the  first  player winning, but rather a search for a
strategy that will lead to a win regardless of what the other  player
does.

	The   simplest  situation  is  characterized  by  a  function
\F1successors\F0 that gives the positions that can be reached in  one
move,  a  predicate  \F1ter\F0  that  tells  when a position is to be
regarded  as  terminal  for  the  given  analysis,  and  a   function
\F1imval\F0  that  gives  a  number  approximating  the  value  of the
position to one of the  players.   We  shall  call  this  player  the
maximizing  player  and  his opponent the minimizing player. Usually,
the numerical values arise, because the search cannot be carried  out
to the end of the game, and the analysis stops with reasonably static
positions that  can  be  evaluated  by  some  rule.   Naturally,  the
function  \F1imval\F2  is  chosen  to  be  easy  to  calculate and to
correlate well with the probability that the  maximizing  player  can
win the position.

	The simplest rule for finding the correct move in a position
uses auxiliary functions
\F1valmax\F0 and \F1valmin\F0 that give a value to a position
by using \F1imval\F0 if the position is terminal and taking the max
or min of the successor positions otherwise.

	For this we want functions for getting the maximum or the
minimum of a function on a list, and they are defined as follows:\.

	\F1maxlis[u,f] ← \F2if n \F1u \F2then \F1-∞ \F2else \F1\;
max[f[\F2a \F1u],maxlis[\F2d \F1u,f]],\F0

and

	\F1minlis[u,f] ← \F2if n \F1u \F2then \F1∞ \F2else \F1\;
min[f[\F2a \F1u],minlis[\F2d \F1u,f]].\F0

\JIn these functions, -∞ and ∞ represent numbers that are smaller and
larger than any actual values that will occur in evaluating \F1f\F0.
If these numbers are not available, then it is necessary to prime
the function with the values of \F1f\F0 applied to the first element
of the list, and the functions are meaningless for null lists.
Iterative versions of the functions are generally better; we give only
the iterative version of \F1maxlis\F0, namely\.

	\F1maxlis[u,f] ← maxlisa[u,-∞,f],\F0

where

	\F1maxlisa[u,x,f] ← \F1if n \F1u \F2then \F1x \F2else \;
		\F1maxlisa[\F2d \F1u,max[x,f[\F2a \F1u]],f].

We now have

	\F1valmax p ← \F2if \F1ter p \F2then \F1imval p \F2else\;
		\F1maxlis[successors p,valmin]\F0,

and

	\F1valmin p ← \F2if \F1ter p \F2then \F1imval p \F2else\;
		\F1minlis[successors p,valmax]\F0.

The best move is now chosen by

	\F1movemax p ← bestmax[succesors p,valmin],\F0

or

	\F1movemin p ← bestmin[succesors p,valmax],\F0

where

	\F1bestmax[u,f] ← bestmaxa[\F2d \F1u,\F2a \F1u,f[\F2a \F1u],f],

	\F1bestmaxa[u,sofar,valsofar,f] ← \F2if n \F1u \F2then \F1sofar
		\F2else if \F1f[\F2a \F1u] ≤ bestsofar \F2then\;
\F1bestmaxa[\F2d \F1u,sofar,bestsofar,f]
		\F2else \F1bestmaxa[\F2d \F1u,\F2a \F1u,f[\F2a \F1u],f],

	\F1bestmin[u,f] ← bestmina[\F2d \F1u,\F2a \F1u,f[\F2a \F1u],f],\F0

and

	\F1bestmina[u,sofar,valsofar,f] ← \F2if n \F1u \F2then \F1sofar
		\F2else if \F1f[\F2a \F1u] ≥ bestsofar \F2then\;
\F1bestmina[\F2d \F1u,sofar,bestsofar,f]
		\F2else \F1bestmina[\F2d \F1u,\F2a \F1u,f[\F2a \F1u],f].\F0

\J	However, this straight minimax computation of the best move does
much more computation in general than is usually necessary.  The simplest
way to see this is from the move tree of Figure 2.6.\.











\CFigure 2.6

\JWe see from this figure that it is unnecessary to examine the moves marked
x, because their values have no effect on the value of the game or on the
correct move since the presence of the 9 is sufficient information at this
point to show that the move leading to the vertex preceding it should not
be chosen by the minimizing player.

	The general situation is that it is unnecessary to examine further
moves in a position once a move is found that refutes moving to the
position in the first place.  This idea is called the αβ-heuristic and
expressed in the following recursive definitions:\.

	\F1maxval p ← maxval1[p,-∞,∞],

	maxval1[p,α,β] ← \F2if \F1ter p \F2then \F1max[α,min[β,imval p]]\;
 \F2else \F1maxval2[successors p,α,β],

	maxval2[u,α,β] ← {minval1[\F2a \F1u,α,β]}[λw. \F2if \F1w ≥ β \F2then\;
 \F1β \F2else \F1maxval2[\F2d \F1u,max[α,w],β]],

	\F1minval p ← minval1[p,-∞,∞],

	minval1[p,α,β] ← \F2if \F1ter p \F2then \F1max[α,min[β,imval p]]\;
 \F2else \F1minval2[successors p,α,β],

	minval2[u,α,β] ← {maxval1[\F2a \F1u,α,β]}[λw. \F2if \F1w ≤ α \F2then\;
 \F1α \F2else \F1minval2[\F2d \F1u,α,min[w,β]].\F0

\J	The reduction in number of positions examined given by the αβ algorithm
over the simple minimax algorithm depends on the order in which the moves are
examined.  In the worst case, the moves happen to be examined in inverse order
of merit in every position on the tree, i.e. the worst move first.  In that case,
there is no improvement over minimax.  The best case is the one in which the
best move in every position is examined first.  If we look \F1n\F0 moves
deep on a tree that has \F1k\F0 successors to each position, then minimax looks
at \F1k\F6n\F0 positions while αβ looks at about only \F1k\F6n/2\F0.  Thus a
program that looks at 10\F64\F0 moves with αβ might have to look at 10\F68\F0
with minimax.  For this reason, game playing programs using αβ make a big
effort to include as good as possible an ordering of moves into the \F1successors\F0
function.  When there is a deep tree search to be done, the way to make the
ordering is with a short look-ahead to a much smaller depth than the main
search.  Still shorter look-aheads are used deeper in the tree, and beyond
a certain depth, non-look-ahead ordering methods are of decreasing complexity.

	A version of αβ incorporating optimistic and pessimistic evaluations
of positions was first proposed by McCarthy about 1958.  Edwards and Hart at
M.I.T. about 1959 proved that the present version of αβ and calculated the
improvement it gives over minimax.  The first publication, however, was
Brudno (1963).  It is worth noting that αβ was not used in the early chess
playing programs in spite of the fact that it is clearly used in any human
play.  Its non-use, therefore, represents a failure of self-observation.
Very likely, there are a number of other algorithms used in human thought
that we have not noticed an incorporated in our programs.  To the extent
that this is so, artificial intelligence will be \F1a posteriori\F0 obvious
even though it is \F1a priori\F0 very difficult.\.